In the past, many floor planning techniques have been implemented in which a number of rectangular blocks or modules are arranged such that they require a minimum amount of area.
For example in U.S. Pat. No. 4,554,625 entitled "Method for Generating an Optimized Nested Arrangement of Constrained Rectangles" issued on Nov. 19, 1985 and assigned to International Business Machines Corporation, a method for generating an overall arrangement of a number of non-overlapping rectangles having constraints on their size and shape is disclosed. The method includes assembling a number of rectangles, each limited by a shape constraint, into one enveloping rectangle, in which the dimensions of the rectangle are to be minimized.
In U.S. Pat. No. 4,918,614 entitled "Hierarchial Floorplanner," issued on Apr. 17, 1990 and assigned to LSI Logic Corporation, a system is described in which logic and/or memory elements are automatically placed on an integrated circuit taking into account the constraints imposed by the logic designer. The system includes means for estimating the size of the elements which have not been laid out and for partitioning groups of elements into successively smaller "slices" of the integrated circuit until all the elements are placed relative to one another. The system also includes means for determining the precise shapes of elements on the integrated circuit based upon the relative placement of such elements and upon the additional area required for routing among such elements. The system attempts to place the elements in such a way that the required amount of area to place all the elements is minimized.
Floor planning or layout design is used in a variety of situations including, but not limited to, architectural planning, computer chip design and any situations in which it is required to place a number of modules or blocks within a minimum amount of area or a prespecified amount of area.
Floor planning is considered quite difficult especially when the solution requires fitting a plurality of modules into a prespecified amount of area, which is not to be altered. The techniques used in situations where the objective is to fit the modules within a minimum amount of area are not successful in solving this problem (of fitting the modules into a prespecified amount of area). Their lack of success is due to the fact that these techniques are incapable of altering the rectangular shape of the modules and thus, they cannot adequately use the permitted amount of space.
Therefore, a need exists for a floor planning technique in which a given number of modules are fit into a predefined area with no overlaps while allowing the modules to deviate from basic rectangular shapes. Further, a need exists for providing such a floor plan in which the spatial constraints of the modules within the layout are satisfied and a given neighborhood relationship is preserved. A further need exists for automating the floor planning technique or layout design such that the modules or blocks may be placed within the predefined area with no overlaps in a relatively short amount of time.